package leetcode71_80;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author shhjiang_001
 * @create 2020-06-21 15:51
 */

            /*
        给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
        示例 1:
        输入:
        [
        [1,1,1],
        [1,0,1],
        [1,1,1]
        ]
        输出:
        [
        [1,0,1],
        [0,0,0],
        [1,0,1]
        ]*/

public class Solution73 {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        ArrayDeque<Integer> rowList = new ArrayDeque<>();
        ArrayDeque<Integer> lineList = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0){
                    rowList.add(i);
                    lineList.add(j);
                }
            }
        }
        while (!rowList.isEmpty()){
            int pop = rowList.pop();
            for (int i = 0; i < n; i++) {
                matrix[pop][i]= 0;
            }
        }
        while (!lineList.isEmpty()){
            int pop = lineList.pop();
            for (int i = 0; i < m; i++) {
                matrix[i][pop] = 0;
            }
        }

    }
}
